package linkedList;

/**
 * 带头（虚拟头节点）单链表
 */
public class LinkdeWithHead {
      private int size;  //当前链表中的有效元素个数，不包括头节点
      private Node dummyHead=new Node();  //真实存在的Node对象，只作为头节点，不存储数据


    /**
     * 删除链表中的所有值为val的元素
     */
    public void removeAllVal(int val){
      Node prev=dummyHead;
      while(prev.next!=null){
          //保证有后继节点
          if (prev.next.val==val){
              //此时prev.next就是待删除的值
              prev.next=prev.next.next;
              size--;
          }else{
              //此时prev.next.val！=val，才可以移动prev
              prev=prev.next;
          }

      }
    }


      /**
       * 删除单链表中索引为index的节点,返回删除前的节点值
       * @param index
       */
      public int  remove(int index){
            if (rangCheck(index)){
                Node prev=dummyHead;
                  for (int i = 0; i <index; i++) {
                        prev=prev.next;
                  }
                  Node node=prev.next;
                  prev.next=node.next;
                  int val=node.val;
                  node.next=null;
                  size--;
                  return val;
          }
            System.err.println("index不在范围没");
                return-1;
      }

      /**
       * 判断index是否合法
       * @param index
       * @return
       */
      private boolean rangCheck(int index) {
            if (index<0||index>=size){
                  return false;
            }
            return true;
      }


    /**
     * 尾插
     * @param val
     */
      public void addLast(int val){
          add(size,val);
      }


      /**
       * 在索引为index的位置插入值为val的节点
       * @param index
       * @param val
       */
      public void add(int index,int val){
           if (index<0||index>size){
                 System.err.println("index不在范围内");
                 return;
           }
           Node prev=dummyHead;
            for (int i = 0; i <index ; i++) {
                  prev=prev.next;
            }
            //prev就是待插入元素的前驱
//            Node node=new Node();
//            node.val=val;
//            node.next=prev.next;
//            prev.next=node;
            Node node=new Node(val,prev.next);
            prev.next=node;    //使用构造方法在产生新节点的同时给node赋值以及连接后继节点
            size++;
      }

      /**
       * 单链表的头插
       * @param val
       */
      public void addFirst(int val){
            Node node=new Node();
            node.val=val;
            node.next=dummyHead.next;
            dummyHead.next=node;

//            Node node=new Node(val,dummyHead.next);  //此处利用构造方法简化代码
//            dummyHead.next=node;

//            dummyHead.next=new Node(val,dummyHead.next);此处使用匿名对象简化代码
            size++;
      }


      /**
       * 链表的打印
       * @return
       */
      public String toString(){
            String ret="";
            Node x=dummyHead.next;
            while(x!=null){
                  ret += x.val;
                  ret  += "->";
                  x=x.next;
            }
            ret+="null";
            return ret;
      }


}



